算法学习Day 1| LeetCode 704. 二分查找、LeetCode 27. 移除元素、LeetCode 977.有序数组的平方

Day1. 704. 二分查找、 27. 移除元素、 977.有序数组的平方

今天总体很简单。

704、基础题，注意elif return 拼写；注意左闭右开re= len(nums)，熟悉一个即可

27、注意优化时间复杂度，快慢指针第一个版本比较舒服，熟悉

977、熟悉官方给出的双指针二和三，尤其是最后一个兄弟的题解，两头往中间计算比较，注意空列表为n个（注意不要打错[]*n），背熟最后一个兄弟的题解

704.二分查找

二分法：

判断target在不在数组中，在返回下标，无-1

易错点：

1、while循环时，L≤(<)R

2、num(middle)>target

right = middle - 1

循环不变量：

左闭右开

左闭右闭

左闭右闭区间：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        le, re = 0, len(nums)-1
        while le < re:
            midd = le + (re-le)//2
            if target < nums[midd]:
                re = midd - 1
            elif target > nums[midd]:
                le = midd + 1
            else:
                return midd
        return -1

左闭右开区间：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        le, re = 0, len(nums)###这里注意
        while le < re:
            midd = le + (re-le)//2
            if target < nums[midd]:
                re = midd 
            elif target > nums[midd]:
                le = midd + 1
            else:
                return midd
        return -1

27.移除元素

1
2
3
4
5
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        return len(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        low = 0  # 慢指针：标记有效元素的位置
        for fast in range(len(nums)):  # 快指针：遍历所有元素
            if nums[fast] != val:
                nums[low] = nums[fast]  # 将非val元素覆盖到左指针位置
                low += 1
        return low  # 返回新长度
        
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 快慢指针
        fast = 0  # 快指针
        slow = 0  # 慢指针
        size = len(nums)
        while fast < size:  # 不加等于是因为，a = size 时，nums[a] 会越界
            # slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow
 # 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
 # nums 的其余元素和 nums 的大小并不重要
 # 相当于直接把不等于的搬到前面

核心逻辑：

  1. 快指针（right）：遍历整个数组，检查每个元素是否为非 val 值。
  2. 慢指针（left）：记录下一个有效元素的位置，只有遇到非 val 元素时才会移动。
  3. 覆盖操作：将非 val 元素直接覆盖到左指针位置，避免反复删除和移动元素。

复杂度对比：

方法 时间复杂度 空间复杂度 适用场景
原代码 O(n²) O(1) 少量 val 元素
双指针法 O(n) O(1) 任意数量 val 元素

为什么双指针法更高效？

(1) 单次遍历

  • 双指针法仅遍历数组一次，而原代码每次 remove(val) 都要遍历一次。
  • 示例：数组 [2, 2, 2, 2]，val=2
    • 原代码：每次 remove(2) 需遍历整个数组，共执行4次 → 总操作次数为 4×4=16。
    • 双指针法：遍历一次，直接覆盖 → 操作次数为4。

(2) 避免频繁内存操作

  • 原代码的 remove() 需要频繁移动后续元素，导致内存操作开销大。
  • 双指针法仅覆盖非 val 元素，无额外内存调整。

总结

  • 原代码问题：理论复杂度应为O(n²)，但LeetCode测试用例可能未覆盖最坏情况，导致误判为O(n)。
  • 改进方法：双指针法通过单次遍历和覆盖操作，真正实现O(n)时间复杂度和O(1)空间复杂度。
  • 建议：以双指针法为标准实现，适用于所有场景。

977. 有序数组的平方

让你设计时间复杂度为O(n)的算法

答案一：复杂度不对

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)。

1
2
3
4
5
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        s = [i*i for i in nums]    
        s.sort()
        return s

官方答案：

方法一：直接排序

思路与算法

最简单的方法就是将数组 nums 中的数平方后直接排序。

1
2
3
4
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。

空间复杂度：O(logn)，除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序。

方法二：双指针

思路与算法

    方法一没有利用「数组 nums 已经按照升序排序」这个条件。显然，如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。

   这样一来，如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。具体地，我们设 neg 为数组 nums 中负数与非负数的分界线，也就是说，**nums[0] 到 nums[neg] 均为负数，而 nums[neg+1] 到 nums[n−1] 均为非负数。**当我们将数组 nums 中的数平方后，那么 nums[0] 到 nums[neg] 单调递减，nums[neg+1] 到 nums[n−1] 单调递增。

   由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置 neg 和 neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#记住这个函数
nums = [-4,-2,-1,1,3,4,6,7 ]
for i, num in enumerate(nums):
    print(i,num)
0 -4
1 -2
2 -1
3 1
4 3
5 4
6 6
7 7

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        negative = -1
        for i, num in enumerate(nums):
            if num < 0:
                negative = i
            else:
                break

        ans = list()
        i, j = negative, negative + 1
        while i >= 0 or j < n:
            if i < 0:
                ans.append(nums[j] * nums[j])
                j += 1
            elif j == n:
                ans.append(nums[i] * nums[i])
                i -= 1
            elif nums[i] * nums[i] < nums[j] * nums[j]:
                ans.append(nums[i] * nums[i])
                i -= 1
            else:
                ans.append(nums[j] * nums[j])
                j += 1

        return ans
###DS注释
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 获取数组长度
        n = len(nums)
        # 初始化最后一个负数的索引为-1（**表示暂未找到负数**）
        negative = -1
        
        # 遍历数组寻找最后一个负数位置（原数组为非递减顺序）
        # 当遇到第一个非负数时即可停止遍历（**后续必然为非负数**）
        for i, num in enumerate(nums):
            if num < 0:
                negative = i  # 更新最后一个负数的位置
            else:
                break  # 遇到非负数循环
        
        ans = list()  # 存储结果的列表
        # 初始化双指针：
        # i指向最后一个负数（可能为-1表示无负数）
        # j指向第一个非负数（可能为n表示无非负数）
        i, j = negative, negative + 1
        
        # 合并两个有序序列（**负数平方递减序列 + 非负数平方递增序列**）
        while i >= 0 or j < n:  # 任意指针有效时继续
            if i < 0:  # 左指针失效（负数已处理完）
                ans.append(nums[j] * nums[j])  # 添加右指针元素的平方
                j += 1
            elif j == n:  # 右指针失效（非负数已处理完）
                ans.append(nums[i] * nums[i])  # 添加左指针元素的平方
                i -= 1
            else:  # 两个指针均有效
                # 比较左右指针元素的平方值（负数平方递减，非负数平方递增）
                left_sq = nums[i] * nums[i]
                right_sq = nums[j] * nums[j]
                if left_sq < right_sq:  # 选择较小的平方值
                    ans.append(left_sq)
                    i -= 1  # 左指针左移（处理前一个负数）
                else:
                    ans.append(right_sq)
                    j += 1  # 右指针右移（处理后一个非负数）
        
        return ans  # 返回合并后的非递减平方序列

"""
时间复杂度分析：
- 找最后一个负数：O(n)
- 双指针合并过程：O(n)
总体时间复杂度：O(n)

空间复杂度分析：
- 存储结果的ans列表：O(n)
- 固定变量存储：O(1)
总体空间复杂度：O(n)

算法特点：
1. 利用原数组有序特性，负数平方后为递减序列，非负数平方后为递增序列
2. 通过双指针归并排序的合并逻辑，避免显式排序（显式排序时间复杂度为O(nlogn)）
3. 处理了全负数/全非负数的边界情况
"""

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
  • 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

方法三：双指针

思路与算法

    同样地，我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，仔细思考其精髓。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        
        i, j, pos = 0, n - 1, n - 1
        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                ans[pos] = nums[i] * nums[i]
                i += 1
            else:
                ans[pos] = nums[j] * nums[j]
                j -= 1
            pos -= 1
        
        return ans

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。
  • 空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

方法三DS代码逐行注释与解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cclass Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)                      # 获取原数组长度
        ans = [0] * n                      # 初始化结果数组，空间复杂度O(n)
        
        i, j, pos = 0, n - 1, n - 1        # 双指针i（左端）、j（右端），pos为结果数组的填充位置
        
        while i <= j:                      # 当左右指针未交叉时继续比较
            left_sq = nums[i] ** 2          # 计算左指针元素的平方
            right_sq = nums[j] ** 2         # 计算右指针元素的平方
            
            if left_sq > right_sq:          # 左平方更大，选择左平方放入结果末尾
                ans[pos] = left_sq
                i += 1                     # 左指针右移
            else:                           # 右平方更大或相等，选择右平方
                ans[pos] = right_sq
                j -= 1                     # 右指针左移
            pos -= 1                       # 结果数组指针前移
        
        return ans                         # 返回非递减排序的平方数组

算法逻辑详解

1. 核心思想

  • 输入数组特性：原数组 nums 是非递减排列的，因此平方后的最大值必然出现在最左端（负数最大）或最右端（正数最大）。
  • 双指针策略：
    1. i从头部开始，处理可能的大负数平方。
    2. j从尾部开始，处理可能的大正数平方。
    3. 从后往前填充结果数组，确保结果是非递减的。

2. 关键步骤

  • 指针初始化：
    • i=0, j=n-1 分别指向数组两端。
    • pos=n-1 标记结果数组的填充位置（从末尾开始）。
  • 循环条件：i <= j 保证所有元素被处理且无遗漏。
  • 平方比较与填充：
    比较 nums[i] 和 nums[j] 的平方值，将较大的存入 ans[pos]，并移动对应指针。
    • 示例：
      若原数组为 [-4, -2, 0, 3, 5]，平方后最大值依次为 16（-4²） 和 25（5²），优先选择25存入末尾。

复杂度分析

类型 说明
时间复杂度 O(n)
空间复杂度 O(n)（结果数组 ans 占用额外空间，与原数组等长）

复杂度推导

  • 时间复杂度：
    • 单次遍历数组，比较和填充操作均为 O(1)，总循环次数为 O(n)。
  • 空间复杂度：
    • 结果数组 ans 的长度为 n → O(n)。
    • 其他变量（i, j, pos）占用常数空间 → O(1)。

示例演示

假设输入 nums = [-4, -2, 0, 3, 5]：

  1. 初始化：i=0, j=4, pos=4
  2. 循环过程：
    • 第1次：比较 -4²=16 和 5²=25 → 存入25，j=3, pos=3
    • 第2次：比较 -4²=16 和 3²=9 → 存入16，i=1, pos=2
    • 第3次：比较 -2²=4 和 3²=9 → 存入9，j=2, pos=1
    • 第4次：比较 -2²=4 和 0²=0 → 存入4，i=2, pos=0
    • 第5次：i=2, j=2 → 比较 0²=0 和 0²=0 → 存入0，j=1, pos=-1
  3. 结果：ans = [0, 4, 9, 16, 25]

算法优势

  1. 无需显式排序：利用原数组有序性，通过双指针合并逻辑避免排序（显式排序时间复杂度为 O(n log n)）。
  2. 边界处理简单：
    • 全负数数组：i 逐步右移，存入所有负数平方的逆序。
    • 全非负数数组：j 逐步左移，直接存入原序平方。
  3. 高效内存利用：仅需一个结果数组，无递归或复杂数据结构。

总结

该代码通过双指针从两端向中间扫描，利用原数组有序性，高效生成平方后的非递减数组。时间复杂度为 O(n)，空间复杂度为 O(n)，适用于大规模数据处理。

一个兄弟的不错题解

双指针：

    由于数组 nums 已经按照非递减顺序排好序，所以数组中负数的平方值是递减的，正数的平方值是递增的。我们可以使用**双指针，分别指向数组的两端**，每次比较两个指针指向的元素的平方值，将较大的平方值放入结果数组的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ans = []
        i, j = 0, len(nums) - 1
        while i <= j:
            a = nums[i] * nums[i]
            b = nums[j] * nums[j]
            if a > b:
                ans.append(a)
                i += 1
            else:
                ans.append(b)
                j -= 1
        return ans[::-1]

时间复杂度 O(n)，其中 n 是数组 nums 的长度。忽略答案数组的空间消耗，空间复杂度 O(1)。

另一个兄弟的不错题解

相向双指针

    实际上，本题考察的并不是如何排序，而是如何使用双指针。

   可以发现，排序的做法 **忽略** 了题目给的一个条件：原数组 nums 非递减排序。如何利用它？对于有序数组来说，如果要查找某个数，或者对数组进行变换，会联想到 **二分** 或者 **双指针**。

在本题中，对应两种思路：

  1. 使用二分去找正数和负数的分界线，然后对两边进行归并
  2. 使用双指针从两边向中间合并，有条理地进行归并
  • 使用二分去找正数和负数的分界线，然后对两边进行归并
  • 使用双指针从两边向中间合并，有条理地进行归并

这里采用后一种方法，毕竟前一种方法还需要找边界接着使用双指针，不如直接使用后一种，节省计算时间。

怎么想到双指针？双指针怎么使用？我们将数组中的数换成 绝对值 来理解，从数组 nums 的两个方向观察，从右往左是递减，从左往右也是递减。这意味着，数组的两头都是大数，中间的是小数。这种 单调性，可以让我们考虑用双指针。

希望得到的答案是从小到大排序的数组。那么，我们完全可以考虑从某个方向去填充这个最终答案。

思路：原数组的双指针从数组的两端开始 相向 移动，而答案的填充从右端开始向左 单向 移动。

做法：假设左指针为l，右指针为 r，填充的指针为 k。

如果左指针的元素绝对值 小于 右指针的元素，说明当前的最大元素为 ∣nums[r]∣，将它平方后放在 ans[k] 的位置

  • 如果左指针的元素绝对值 小于 右指针的元素，说明当前的最大元素为 ∣nums[r]∣，将它平方后放在 ans[k] 的位置

    这种思路为什么正确？上面已经指出，从绝对值的角度来看，数组的数表现为 *中间小两头大* 的分布。使用双指针遍历，选择它俩中的最大值，一定是 nums 中 **剩余所有数** 中的最大，平方后放入答案即可。当然，这也侧面解释了为什么答案的填充也是从右往左。

细节：具体实践时，比较绝对值可以换成比较平方值，一样的效果，后者能直接放入答案，更加方便。

将上面的推导转为代码，已附加注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#熟悉这个for k in range(n - 1, -1, -1)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 相向双指针
        n = len(nums)
        ans = [0] * n#@##注意不能用[]*n,否则为空列表
        i, j = 0, n - 1  # 左右指针
        for k in range(n - 1, -1, -1):  # 从后往前开始填充结果数组
            x = nums[i] * nums[i]
            y = nums[j] * nums[j]
            if x > y:  # 更大的数放右边
                ans[k] = x
                i += 1
            else:
                ans[k] = y
                j -= 1
        return ans

  • 时间复杂度： O(n)，其中 n 为数组 nums 的长度，一次遍历
  • 空间复杂度： O(1)，同理不考虑存储答案的数组 ans 的空间开销